package com.cdream.basic.algorithm.leetcode.array;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * @author cdream
 * @date 2022/1/13
 */
public class Question747 {
    public int dominantIndex(int[] nums) {
        if(nums.length==1){
            return 0;
        }
        int max = 0;
        int secmax = -1;
        for(int i = 0; i<nums.length; i++){
            if(nums[max] < nums[i]){
                secmax = max;
                max = i;
            }
            if(max!=i && (secmax ==-1 || nums[i]>nums[secmax])){
                secmax = i;
            }
        }
        return (nums[secmax] == 0 || nums[max]/nums[secmax] >=2) ? max : -1;

    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((k1, k2)-> nums1[k1[0]]+nums2[k1[1]]-nums1[k2[0]]-nums2[k2[1]]);
        for(int i = 0; i<=Math.min(k,nums2.length-1);i++){
            pq.offer(new int[]{i,0});
        }
        List<List<Integer>> res = new ArrayList<>();
        while(k-->0 && !pq.isEmpty()){
            int[] top = pq.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[top[0]]);
            list.add(nums2[top[1]]);
            res.add(list);
            pq.offer(new int[]{top[0],top[1] + 1});
        }
        return res;
    }

    public static void main(String[] args) {
        // new Question747().kSmallestPairs(new int[]{1,2},new int[]{3},3);
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            System.out.println(random.nextInt(10));
        }
    }
}
